package graphs;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

/**
 * Class for a (simple) graph
 * Check documentation in interface IGraph
 * @author Ballarini Robin, Chatelain Julie, Antoine Walsdorff
 * @version 16/12/2013
 */
public class Graph<T extends Comparable<T>,E> implements IGraph<T,E>{

	/** Liste des noeuds*/
	private ArrayList<Vertex<T,E>> vertices;

	/** Liste des aretes*/
	private ArrayList<Edge<T,E>> edges;

	/**
	 * Construit un graphe vide (sans noeud et sans arete)
	 * 
	 */
	public Graph(){
		vertices=new ArrayList<Vertex<T,E>>();
		edges=new ArrayList<Edge<T,E>>();
	}

	public Iterable<Vertex<T,E>> vertices(){
		return vertices;
	}

	/**
	 * Cette methode retourne le noeud dont l'identifiant est id 
	 * s'il appartient a this, retourne null sinon
	 * 
	 * @param id l'identifiant d'un noeud
	 * @return le noeud d'identifiant id de this, ou null
	 */
	public Vertex<T,E> getVertex(E id){
		Iterable<Vertex<T,E>> l=vertices();
		Iterator<Vertex<T,E>> it=l.iterator();
		Vertex<T,E> temp;
		while(it.hasNext()){
			temp=it.next();
			if((temp.getID()).equals(id)){
				return temp;
			}
		}
		return null;
	}

	public Iterable<Edge<T,E>> edges(){
		return edges;
	}

	public Iterable<Edge<T,E>> incidentEdges(Vertex<T,E> v){
		return v.getInc();
	}

	public Vertex<T,E> opposite(Vertex<T,E> v, Edge<T,E> e) throws GraphException{
		Vertex<T,E> one=e.getFirstVertex();
		Vertex<T,E> two=e.getSecondVertex();
		boolean a=one.getID().equals(v.getID());
		boolean b=two.getID().equals(v.getID());
		if(!a && !b){
			throw new GraphException("vertex v not adjacent to edge e : opposite method call (Graph.java)");
		}
		if(a && !b){
			return two;
		}
		if(!a && b){
			return one;
		}
		if(a && b){
			throw new GraphException("Error in opposite method call (Graph.java) : graph not simple or structure error");
		}
		return null;
	}

	public List<Vertex<T,E>> endVertices(Edge<T,E> e){
		return e.getVertex();
	}

	public boolean areAdjacent(Vertex<T,E> v, Vertex<T,E> w){
		if(v==w){
			return false;
		}

		List<Edge<T,E>> elist=v.getInc();
		for(Edge<T,E> ed : elist){
			Vertex<T,E> one=ed.getFirstVertex();
			Vertex<T,E> two=ed.getSecondVertex();
			if(one==w || two==w){
				return true;
			}
		}
		return false;
	}

	public E replace(Vertex<T,E> v, E id){
		E res=v.getID();
		v.setID(id);
		return res;
	}

	public T replace(Edge<T,E> e, T weight){
		T res=e.getWeight();
		e.setWeight(weight);
		return res;
	}

	public Vertex<T,E> insertVertex(E id){
		Vertex<T,E> ver=new Vertex<T,E>(id,vertices.size());
		vertices.add(ver);
		return ver;
	}

	public Edge<T,E> insertEdge(Vertex<T,E> v, Vertex<T,E> w, T weight){
		Edge<T,E> n=new Edge<T,E>(v,w,weight,edges.size());
		edges.add(n);
		return n;
	}

	public T removeEdge(Edge<T,E> e){
		edges.remove(e);
		Vertex<T,E> one=e.getFirstVertex();
		Vertex<T,E> two=e.getSecondVertex();
		one.getInc().remove(e);
		two.getInc().remove(e);
		return e.getWeight();
	}

	public E removeVertex(Vertex<T,E> v){
		List<Edge<T,E>> r=v.getInc();
		for(Edge<T,E> e : r){
			removeEdge(e);
		}
		vertices.remove(v);
		return v.getID();
	}

	
	// Variables utiles a la methode Kruskal --v

	private int[] previousNodes;

	public final Comparator<Edge<T,E>> weightComparator = new Comparator<Edge<T,E>>(){

		public int compare(Edge<T,E> c1, Edge<T,E> c2) {
			return c1.getWeight().compareTo(c2.getWeight());
		}
	};

	@SuppressWarnings("unchecked")
	/*
	 * Algorithme de Kruskal : cree un ensemble de plusieurs villes et
	 * regarde les aretes de poids le plus faible et ajoute le noeud
	 * relie a l'ensemble par l'arete de poids le plus faible a l'ensemble
	 * @author Ludovic Fastre
	 */
	public Graph<T,E> kruskalAlgo(){
		Graph<T,E> kruskalList = new Graph<T,E>();

		int nbrCities = ((List<Vertex<T,E>>)vertices()).size();

		if (nbrCities <= 0) {
			System.out.println("Nombre de noeuds du graphe <= 0");        
		}

		previousNodes = new int[nbrCities];
		int[] size = new int[nbrCities];

		for (int i=0; i<nbrCities; i++) {
			previousNodes[i] = i;
			size[i] = 1;
		}

		int nbrEdges = ((List<Edge<T,E>>)edges()).size();
		int indice = 0;
		Edge<T,E> currentEdge;

		// Tri des aretes en fonction du poids
		List<Edge<T,E>> triEdges = ((List<Edge<T,E>>)edges());
		Collections.sort(triEdges, weightComparator);

		// boucle tant que toutes les villes n'ont pas ete ajoutees a l'ensemble
		// et tant que toutes les aretes n'ont pas ete visitees
		while (!isCompleted(size, nbrCities) && indice<nbrEdges ){

			// Extention de la "zone de recherche"
			currentEdge = (Edge<T,E>) (triEdges.toArray()[indice]);
			int a = find(currentEdge.getFirstVertex().getPosition());
			int b = find(currentEdge.getSecondVertex().getPosition());

			if(a != b){ 
				kruskalList.insertEdge(currentEdge.getFirstVertex(), currentEdge.getSecondVertex(), currentEdge.getWeight());

				int pNode1 = find(a);
				int pNode2 = find(b);

				// Regarde si a et b sont deja dans le meme ensemble
				if (pNode1 != pNode2) {
					if (size[pNode1] >= size[pNode2]) {
						size[pNode1] += size[pNode2];
						previousNodes[pNode2] = pNode1;
					} else {
						size[pNode2] += size[pNode1];
						previousNodes[pNode1] = pNode2;
					}
				}                      
			}

			indice++;
		}
		return kruskalList;
	}
	
	/*
	 * Methode qui renvoie le noeud de "l'ensemble de Kruskal"
	 * @author Ludovic Fastre
	 */
	private int find(int pNode){

		if (this.previousNodes[pNode] == pNode) {
			return pNode;
		} else {
			int previousNode = find(this.previousNodes[pNode]);

			// 1 ou + liens entre node precedent et actuel
			if (previousNode != this.previousNodes[pNode]) {
				this.previousNodes[pNode] = previousNode;
				return previousNode;

			} else {
				return previousNode;
			}
		}
	}
	
	/*
     * Retourne false si toutes les villes n'ont pas ete ajoutees a l'ensemble
     * @author Ludovic Fastre
     */
    boolean isCompleted(int[] size, int nbrCities) {
            for (int i = 0 ; i<size.length ; i++) {
                    if (size[i] == nbrCities)
                            return true;
            }
            return false;
    }
}
